A device seeking to access a combination of services provided by another device in a network environment, such as a wireless network environment, may engage in a pre-association discovery procedure to identify a device in the network that can provide the combination of the services of interest. The pre-association discovery procedure may utilize messages, e.g. probe request/response messages, beacon messages, etc., that are transmitted using a robust modulation and coding scheme with a low data rate to provide the highest level of protection for the messages. The device may transmit a request message that indicates the services of interest, and devices in the network may transmit a response message if they can provide any of the individual services of interest. Thus, the device seeking to access the combination of services may need to transmit/receive multiple low data rate pre-association discovery messages with each responding device in order to identify a devices that can provide the desired combination of services, which may occupy a significant amount of bandwidth in the network environment while also resulting in latency before the combination of services can be accessed.